package ch18._10;

import java.util.*;

import ch18.Util;

public class Solution {

	public static List<String> transform(String start, String end,
			Set<String> dictionary) {
		Map<String, String> trackBackMap = new HashMap<String, String>();
		Deque<String> queue = new LinkedList<String>();
		Set<String> visited = new HashSet<String>();
		queue.add(start);
//		visited.add(start);
		boolean found = false;
		while (!queue.isEmpty()) {
			String top = queue.removeLast();
			if (top.equals(end)) {
				found = true;
				break;
			}
			if (visited.contains(top)) {
				continue;
			}
			visited.add(top);
			Set<String> set = addAllByChangingOneLetter(top);
			// queue.addAll(set);
			for (String s : set) {
				if (!visited.contains(s) && dictionary.contains(s)) {
					queue.addFirst(s);
					trackBackMap.put(s, top);
//					visited.add(s);
				}
			}
		}
		List<String> result = null;
		if (found) {
			result = new ArrayList<String>();
			String key = end;
//			while (trackBackMap.containsKey(key)) {
			while (key != null) {
				result.add(0, key);
				key = trackBackMap.get(key);
			}
			return result;
		}
		return result;
	}

	private static Set<String> addAllByChangingOneLetter(String s) {
		char[] array = s.toLowerCase().toCharArray();
		Set<String> set = new HashSet<String>();
		for (int i = 0; i < array.length; i++) {
			char ch = array[i];
			// for (int i = (int)('a'); i <= (int)('z'); i++) {
			for (char letter = 'a'; letter <= 'z'; letter++) {
				if (letter == ch) {
					continue;
				} else {
					array[i] = letter;
					String str = new String(array);
					set.add(str);
				}
			}
			array[i] = ch;
		}
		return set;
	}

	public static Set<String> makeDictionary(String[] words) {
		Set<String> dict = new HashSet<String>();
		for (String word : words) {
			dict.add(word);
		}
		return dict;
	}

	public static void main(String[] args) {
		String[] words = { "maps", "tan", "tree", "apple", "cans", "help",
				"aped", "free", "apes", "flat", "trap", "fret", "trip", "trie",
				"frat", "fril" };
		Set<String> dictionary = makeDictionary(
				Util.getBigArray()
//				words
				);
		String start = "tree";
		String end = "flat";
		List<String> result = transform(start, end, dictionary);
		System.out.println(result.toString());
	}
}